#include <functional>
#include <iostream>
#include <vector>

class Solution {
  public:
    int movingCount(int m, int n, int k) {
        int result = 0;
        std::vector<std::vector<bool>> flag(m, std::vector<bool>(n, false));
        std::function<void(int, int)> helper;

        helper = [&](int x, int y) {
            if (x >= m or y >= n or flag[x][y]) return;
            if (sum_below(x, y, k))
                ++result;
            else
                return;
            std::cout << x << ", " << y << std::endl;
            flag[x][y] = true;
            helper(x + 1, y);
            helper(x, y + 1);
        };
        helper(0, 0);
        return result;
    }

  private:
    bool sum_below(int i, int j, int k) {
        int sum = 0;
        if (i < 10) {
            sum += i;
        } else {
            sum += i % 10 + i / 10;
        }
        if (j < 10) {
            sum += j;
        } else {
            sum += j % 10 + j / 10;
        }
        return sum <= k;
    }
};

int main() {
    Solution s;
    //    std::cout << s.movingCount(3, 2, 17) << '\n';
    std::cout << s.movingCount(16, 8, 4) << '\n';
    return 0;
}
